N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
题目解释:国际象棋的棋子皇后,可以横向纵向和斜向吃掉对方棋子,题目的目标是一个NxN的棋盘上放置n个皇后并且不会相互攻击到彼此
典型backtrack场景,多选择问题
backtrack三要素:
- 目的
- 约束
- 选择
回归到这道题上来看:
- 目的:放置n个皇后
- 约束:皇后之间两两不能攻击
- 选择:按行逐个逐个尝试
本期使用c++
目的:
if (row == n)
count++;
约束: 显然每一行只能有一个皇后,然后就剩下比较纵向和斜向是否可行 等于0是纵向,等于rowid - i是斜向
bool isvalid(std::vector<int> place)
{
int rowid = place.size() - 1;
for (int i = 0; i < rowid; i++)
{
int diff = abs(place[i] - place[rowid]);
// 等于0是纵向,等于rowid - i是斜向
if (diff == 0 || diff == rowid - i)
return false;
}
return true;
}
选择: 每一行逐一尝试
for (int i = 0; i < row; i++)
{
place.push_back(i);
if (isvalid(place))
{
backtrack(row, n, count, place);
}
place.pop_back();
}
完整代码
#include <vector>
class Solution
{
public:
int totalNQueens(int n)
{
int count = 0;
std::vector<int> place;
backtrack(n, 0, count, place);
return count;
}
private:
bool isvalid(std::vector<int> place)
{
int rowid = place.size() - 1;
for (int i = 0; i < rowid; i++)
{
int diff = abs(place[i] - place[rowid]);
if (diff == 0 || diff == rowid - i)
return false;
}
return true;
}
void backtrack(int row, int n, int &count, std::vector<int> &place)
{
if (row == n)
count++;
else
{
n++;
for (int i = 0; i < row; i++)
{
place.push_back(i);
if (isvalid(place))
{
backtrack(row, n, count, place);
}
place.pop_back();
}
}
}
};